package demo2;


import java.util.Stack;

public class Solution {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value){
            this.val = value;
        }
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        TreeNode B = new TreeNode(5);
        TreeNode C = new TreeNode(1);
        TreeNode D = new TreeNode(6);
        TreeNode E = new TreeNode(2);
        TreeNode F = new TreeNode(0);
        TreeNode G = new TreeNode(8);
        TreeNode H = new TreeNode(7);
        TreeNode I = new TreeNode(4);

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = null;
        D.right = null;
        E.left = H;
        E.right = I;
        F.left = null;
        F.right = null;
        G.left = null;
        G.right = null;
        H.left = null;
        H.right = null;
        I.left = null;
        I.right = null;

//        A.left = B;
//        A.right = C;
//        B.left = null;
//        B.right = null;
//        C.left = null;
//        C.right = null;

        TreeNode father = lowestCommonAncestor(A,C,G);
        System.out.println(father.val);
        System.out.println(" yut");
    }

//    法一：复杂代码
//    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root == null) {
//            return null;
//        }
//
//        //初始准备
//        Stack<TreeNode> ps = new Stack<>();
//        TreeNode pre1 = null;
//        TreeNode cur1 = root;
//        Stack<TreeNode> qs = new Stack<>();
//        TreeNode pre2 = null;
//        TreeNode cur2 = root;
//
//        // 获取两个节点的路劲
//        while(cur1 != null || !ps.isEmpty()){
//            if(cur1 == p){
//                ps.push(cur1);
//                break;
//            }
//
//            if(cur1 != null){
//                ps.push(cur1);
//                cur1 = cur1.left;
//            }else{
//                TreeNode top = ps.peek();
//                if(top.right == null || top.right==pre1){
//                    cur1 = ps.pop();
//                    pre1 = cur1;
//                    cur1 = null;
//                }else{
//                    cur1 = top.right;
//                }
//            }
//        }
//        while(cur2 != null || !qs.isEmpty()){
//            if(cur2 == q){
//                qs.push(cur2);
//                break;
//            }
//
//            if(cur2 != null){
//                qs.push(cur2);
//                cur2 = cur2.left;
//            }else{
//                TreeNode top = qs.peek();
//                if(top.right == null || top.right==pre2){
//                    cur2 = qs.pop();
//                    pre2 = cur2;
//                    cur2 = null;
//                }else{
//                    cur2 = top.right;
//                }
//            }
//        }
//
//        // 让两个栈的size和小栈的size相等
//        int psize = ps.size();
//        int qsize = qs.size();
//        if(psize > qsize){
//            int size = psize - qsize;
//            while(size>0){
//                ps.pop();
//                size--;
//            }
//
//        }else{
//            int size = qsize - psize;
//            while(size>0){
//                qs.pop();
//                size--;
//            }
//        }

    // 法二：简化代码
//    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root == null) {
//            return null;
//        }
//
//        //初始准备+把数据入栈(利用getPath方法)
//        Stack<TreeNode> ps = new Stack<>();
//        getPath(root,p,ps);
//        Stack<TreeNode> qs = new Stack<>();
//        getPath(root,q,qs);
//
//        // 让两个栈的size和小栈的size相等
//        int psize = ps.size();
//        int qsize = qs.size();
//        if(psize > qsize){
//            int size = psize - qsize;
//            while(size>0){
//                ps.pop();
//                size--;
//            }
//
//        }else{
//            int size = qsize - psize;
//            while(size>0){
//                qs.pop();
//                size--;
//            }
//        }
//
//        // 从两个栈中依次取出元素比较，元素相等，就是原始两个节点p和q的公共祖先
//        while (!ps.isEmpty()){
//            TreeNode ptnode = ps.pop();
//            TreeNode qtnode = qs.pop();
//            if(ptnode == qtnode){
//                return ptnode;
//            }
//        }
//        return null;
//    }
//    private static boolean getPath(TreeNode root,TreeNode node, Stack<TreeNode> stack){
//        // 1、既作为开始判断，有作为递归过程中的判断。
//        if(root == null || node == null){
//            return false;
//        }
//        // 2、在下一步当前节点返回上一层递归前，入栈截至节点
//        stack.push(root);
//        // 3、满足条件，开始递归返回
//        if(root == node){
//            return true;
//        }
//        // 4、在每一层递归里，走到这里说明root!=null && root!=node。所以递归看当前节点的左右子树
//        boolean left = getPath(root.left,node,stack);
//        if(left == true){
//            return true;
//        }
//        boolean right = getPath(root.right,node,stack);
//        if(right == true){
//            return true;
//        }
//
//        // 5、到这里说明当前节点左右子树中都没找到
//        //    但是当前节点以及入栈，所以先出栈，在返回false
//        stack.pop();
//        return false;
//    }
//}

    // 法二：分情况讨论
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 这里代表找到了树的当前方向的尽头
        // 比如到了叶子节点的左右子树，则返回null
        if(root == null || p == null || q == null){
            return null;
        }
        // 第一种情况：p和q有一个在根节点
        // 还有一个含义是：满足条件时返回这个节点或者q
        if(root == p || root == q){
            return root;
        }

        // 走到这里，说明 root!=null && p!=null &&q!=null，且p和q均不是根节点。
        // 进入递归查看左右子树
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        //第二种：p和q在root两边
        if(leftNode != null && rightNode != null){
            return root;
        }
        // 第三种：p和q在root的同一侧，且都不在根节点
        // 重点注意：如果都在root的右侧，那先找到的那一个节点就是最近公告祖先
        else if (leftNode != null) {
            return leftNode;
        } else if (rightNode != null) {
            return rightNode;
        }else{
            // 注意：这一步是为了防止p和q都在某个节点的右侧时发生错误。
            //  也可以理解为已经访问的节点没找到p或者q的标记,比如访问到叶子节点，但它不是p或者q
            return null;
        }
    }
}


class Solution2 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    // 二叉搜索树与双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        convertChild(pRootOfTree);

        // 找到二叉搜索树改变为双向链表的头，并返回
        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        return head;
    }

    // 这个prev要定义在递归之外，相当于指针传地址，改变指针指向
    private TreeNode prev = null;
    // 递归方法实现前驱后继的改变
    private void convertChild(TreeNode pcur){
        if(pcur == null){
            return ;
        }

        convertChild(pcur.left);
        pcur.left = prev;
        if(prev != null){  // 注意：排除中序遍历第一个节点执行下面一行代码时，空指针异常
            prev.right = pcur;
        }
        prev = pcur;
        convertChild(pcur.right);
    }
}
